Ray tracing is becoming an important alternative as a rendering method in high-performance interactive applications. This includes industrial and scientific three-dimensional visualization, but also extends to non-graphical applications like collision detection or the simulation of sound wave propagation. One of the most interesting and technically demanding possible use cases is rendering in computer games, which requires very high and constant image refresh rates combined with highly dynamic content. These performance requirements are particularly difficult to meet in a ray tracing environment.
One aspect that makes ray tracing more difficult to use as compared to traditional triangle rasterization is the fact that some kind of spatial index data structure has to be constructed before rendering can begin. Index (or acceleration) structures are used to perform visibility culling operations by enabling early rejection of large parts of a scene that are not visible (e.g., objects that are occluded by a wall). Without such data structures, tracing a single ray would take linear time in the number of geometric primitives in the scene, which is too costly in almost all scenarios. Since constructing the required data structures comes at a certain cost as well, it has to be carefully evaluated when and for which parts of the scene to execute a build. Moreover, not all types of data structures are equally well suited in different contexts. Usually, the challenge is to find a good tradeoff between construction speed and ray-geometry intersection performance.
Constructing an acceleration data structure over all the geometric primitives in the scene from scratch each frame is usually infeasible, as this essentially requires a sorting process. Thus, interactive ray tracing applications typically employ a hierarchical scene graph like structure to represent the scene organization, including geometric primitives and spatial indices. Only when changes are detected, data structures are actually rebuilt or updated at different hierarchy levels.
FIG. 1 illustrates a conventional hierarchical structure 100 for performing ray tracing operations known in the art. The conventional hierarchical structure includes the following basic node types that are relevant in terms of interaction with acceleration structures:                Group nodes 120, 140 allow other nodes to be attached as children. This represents a region of a scene which is to be rendered and the union of all children. Each group node owns an acceleration data structure built over child bounding volumes.        Transform nodes 1121-112n, 130, 150 represents a space transformation of the sub-tree below the transform node.        Geometry nodes 1101-110n hold a geometric object, along with an acceleration structure built over the primitives of the object. The geometric object includes a list of primitives which define a geometry included in the region represented by the highest level group node 140, which is referred to as the hierarchical group node.        
The conventional hierarchical structure 100 is organized, such that the highest group node 140 represents the region of a scene which is to be rendered. Each of the geometry nodes 1101-110n, 160 includes a plurality of primitives that collectively define a particular geometry. A group node 120 is constructed over several geometry nodes 1101-110n, and defines an instantiation or graphical rendering of the combined geometries which are defined by each of the geometry objects 1101-110n. A sole geometry node 160 provides a second geometry that is included within the region represented by the hierarchical group node 140.
As shown, the conventional hierarchical structure 100 implements an acceleration structure in each group 120, 140 and geometry node 1101-110n, 160. Further particularly, the acceleration structures in geometry node are constructed over the geometric primitives of the node, while the acceleration structures in the groups are built over the bounding volumes (usually axis-aligned bounding boxes) of the underlying children.
For the vast majority of use cases, building acceleration structures at the group level is much cheaper compared to building acceleration structures at the geometry object level, as the number of elements to consider at the group level is much lower. As a consequence, some systems rebuild only the top-level structure every frame while not allowing rebuilds of the lower level geometry at all. In such an instance, however, only rigid transformations are efficiently supported. For non-rigid transformations, geometry objects have to be explicitly replaced by new geometry. Other systems do permit some additional flexibility, allowing, for example, arbitrary hierarchy depth, or incremental updates of acceleration structures in order to support deformation of geometry. However, these systems still operate using the same principle of associating one acceleration structure with each geometry node and each group node. Such an arrangement however requires a rebuild of the acceleration within the geometry nodes 1101-110n, 160 whenever there is a change in the geometry defined by the geometry nodes, such a rebuild being computationally expensive and time consuming.